/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "str.h"
#include "idx.h"
//---------------------------------------------------------------------------
static void index_delete_key(
  struct index_link * link,
  uint32_t position,
  void * data)
{
  uintptr_t entry_size = link->idx->entries_sizes[link->blk->type];
  uint8_t * p = link->blk->keys + position * entry_size;

#if COMPILE_RUNTIME_CHECKS
  if( position >= link->blk->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  //if( link->blk->count > link->idx->blk_max_keys[link->blk->type] ){
  //  fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
  //  abort();
  //}
#endif

  if( link->blk->type == INDEX_LEAF ){
    if( data != NULL )
      memcpy(data,p + link->idx->key_size,link->idx->data_size);
  }
  else if( link->blk->type == INDEX_NODE ){
#if COMPILE_RUNTIME_CHECKS
    if( data != NULL ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
  }
  else {
    errno = EINVAL;
#if COMPILE_RUNTIME_CHECKS
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
#endif
    return;
  }

  memcpy(p,p + entry_size,(link->blk->count - position - 1) * entry_size);

#if COMPILE_RUNTIME_CHECKS
  memset(link->blk->keys + (link->blk->count - 1) * entry_size,0,entry_size);
#endif

  if( --link->blk->count > 0 && position == 0
      && !bsint_is_zero(&link->block_index,link->idx->block_index_size) )
    link->zero_position_changed = true;
}
//---------------------------------------------------------------------------
static void remove_prev_link(
  struct index * idx,
  struct index_link * prev_link,
  struct index_link * link)
{
  uintptr_t i;

#if COMPILE_RUNTIME_CHECKS
  if( prev_link->blk->type != INDEX_NODE ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif
  for( i = 0; i < prev_link->blk->count; i++ ){
    if( memcmp(index_block_link(prev_link,i),&link->block_index,idx->block_index_size) == 0 ){
      index_delete_key(prev_link,i,NULL);
      return;
    }
  }
#if COMPILE_RUNTIME_CHECKS
  if( i == prev_link->blk->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif
}
//---------------------------------------------------------------------------
void index_gather_block(struct index * idx,struct index_link * root,struct index_link * link)
{
  intptr_t i;
  struct index_link_change change, * p_change;
  struct index_btree_stack_entry e;

  if( link->blk->count > 0 && !link->zero_position_changed ) return;

  if( link != root ){
    if( bsint_is_zero(&link->blk->prev_block_index,idx->block_index_size) ){
      e.link = root;
    }
    else {
      e.link = index_link_block(idx,&link->blk->prev_block_index);
      if( errno != 0 ) return;
    }

    if( link->blk->count == 0 ){
      remove_prev_link(idx,e.link,link);
      link->zero_position_changed = false;

      if( e.link->blk->count == 0 ){
        change.link = e.link;
        change.what = e.link == root ? ILC_UPD : ILC_DEL;
        e.link->blk->type = INDEX_LEAF;
        i = array_lookup_insert_copy(&idx->changed_links,&change);
        if( i >= 0 && change.what == ILC_DEL ){
          p_change = array_get(&idx->changed_links,i);
          p_change->what = change.what;
        }
      }
    }
    else if( link->zero_position_changed ){
      index_lookup_key(&e,link->blk->keys,0);
#if COMPILE_RUNTIME_CHECKS
      if( memcmp(index_block_link(e.link,e.next_level_position),&link->block_index,idx->block_index_size) != 0 ){
        DEBUG_index_dump_block_keys(stderr,e.link);
        fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
        abort();
      }
#endif
      memcpy(index_block_entry(e.link,e.next_level_position),link->blk->keys,idx->key_size);
      if( e.next_level_position == 0 && e.link != root ) e.link->zero_position_changed = true;
      link->zero_position_changed = false;

      change.link = e.link;
      change.what = ILC_UPD;

      array_lookup_insert_copy(&idx->changed_links,&change);
    }

    index_gather_block(idx,root,e.link);

    if( e.link != root ){
      mutex_acquire(&idx->cache->links_mutex);
      e.link->linked--;
      mutex_release(&idx->cache->links_mutex);
    }
  }
}
//---------------------------------------------------------------------------
void index_gather(
  struct index * idx,
  struct index_btree_stack * stack,
  const void * key,
  void * data)
{
  int err = ENOENT;
  struct index_btree_stack_entry * e;

  index_get_key_path(idx,stack,key,0);

  e = array_get(&stack->entries,stack->sp);

  if( errno != 0 ){
    err = errno;
  }
  else if( e->c == 0 ){
    rwlock_acquire_read_lock(&idx->changed_links_lock);

    rwlock_upgrade(&e->link->lock);
    e->link_lock = RWL_WRITE;

    index_delete_key(e->link,e->position,data);

    e->link_change = e->link->blk->count > 0 ? ILC_UPD : ILC_DEL;

    err = 0;

    rwlock_upgrade(&idx->changed_links_lock);
    index_unwind_stack(idx,stack,RWL_NONE);
    rwlock_release_write_lock(&idx->changed_links_lock);
  }
  errno = err;
}
      //while( sp > 0 ){
      //  uintptr_t half;
      //  
      //  t = array_get(&stack->entries,--sp);

      //  if( e->link_change != ILC_NONE && e->next_level_position == 0 ){
      //    memcpy(index_block_entry(t->link,t->next_level_position),e->link->blk->keys,idx->key_size);
      //    t->link_change = ILC_UPD;
      //  }

      //  half = idx->blk_max_keys[e->link->blk->type] / 2;

      //  if( e->link->blk->count == 0 ){
      //    index_delete_key(t->xlink,t->next_level_position,NULL); // delete link in top level
      //    // if delete last link from root then set root block type to leaf
      //    if( sp == 0 && t->link->blk->count == 0 )
      //      t->link->blk->type = INDEX_LEAF;
      //    t->link_change = ILC_UPD;
      //    e->link_change = ILC_DEL;
      //  }
      //  else if( e->link->blk->count < half ){
      //    // try to move all keys to top level block
      //    if( t->link->blk->type == e->link->blk->type
      //        && t->link->blk->count + e->link->blk->count - 1 <= idx->node_max_key_count ){
      //      index_copy_paste_keys(t->link,t->next_level_position + 1,e->link,1,e->link->blk->count - 1);
      //      memcpy(index_block_link(t->link,t->next_level_position),
      //        e->link->blk->keys + idx->key_size,idx->block_index_size);
      //      t->link_change = ILC_UPD;
      //      e->link_change = ILC_DEL;
      //    }
      //    //else {
      //    //  uintptr_t space = e->left != NULL ? idx->blk_max_keys[e->left->blk->type] - e->left->blk->count : 0;

      //    //  // try to distribute all keys to left neighbor
      //    //  if( e->link->blk->count <= space ){
      //    //    index_copy_paste_keys(e->left,e->left->blk->count,e->link,0,space);
      //    //    e->left_change = ILC_UPD;
      //    //    index_delete_key(t->link,t->next_level_position,NULL); // delete link in top level
      //    //    t->link_change = ILC_UPD;
      //    //    e->link_change = ILC_DEL;
      //    //  }
      //    //  else {
      //    //    uintptr_t overhalf;

      //    //    // try to distribute keys from left neighbor
      //    //    if( e->left != NULL ){
      //    //      half = idx->blk_max_keys[e->left->blk->type] / 2;
      //    //      overhalf = e->left->blk->count - half;
      //    //      
      //    //      if( overhalf > 0 ){
      //    //        index_cut_paste_keys(e->link,0,e->left,half,overhalf);
      //    //        e->left_change = ILC_UPD;
      //    //        memcpy(index_block_entry(t->link,t->next_level_position),e->link->blk->keys,idx->key_size);
      //    //        t->link_change = ILC_UPD;
      //    //        e->link_change = ILC_UPD;
      //    //      }
      //    //    }

      //    //    half = idx->blk_max_keys[e->link->blk->type] / 2;
      //    //    if( e->link->blk->count < half ){ // and now what i may do?
      //    //      e = e;
      //    //    }
      //    //  }
      //    //}
      //  }
      //  e = t;
      //}
//---------------------------------------------------------------------------
